package com.哈希表;


import java.util.*;

/**
 * 设计键值对
 * @param <K>
 * @param <V>
 */
class Pair<K,V>{
    public K key;
    public V value;
    public Pair(K key,V value){
        this.key = key;
        this.value = value;
    }
}

/**
 * 设计桶
 */
class MyBucket<T>{
    LinkedList<Pair<T,T>> pairs;
    public MyBucket(){
        this.pairs = new LinkedList<>();
    }
    public void save(T key,T value){

        for(Pair pair:pairs){
            if(Objects.equals(key,value)){
                pair.value = value;
                return;
            }
        }

           pairs.add(new Pair<>(key,value));

    }
    public void remove(T key){
        for(Pair pair:pairs){
            if(pair.key.equals( key)){
                pairs.remove(pair);
                return;
            }
        }
    }
    public Integer get(T key){
        for(Pair pair:pairs){
            if(pair.key.equals( key)){
                return (Integer) pair.value;
            }
        }
        return -1;
    }
}

/**
 * 哈希映射
 */
public class MyHashMap<T> {
    int range ;
    ArrayList<MyBucket> buckets;
    Set<T> keys;
    /** Initialize your data structure here. */
    public MyHashMap() {
        keys = new HashSet<>();
        range = 2069;
        buckets = new ArrayList<>();
        for(int i = 0;i<range;i++){
            MyBucket bucket = new MyBucket();
            buckets.add(bucket);
        }
    }
    public int _hase(T key){
        return (Integer)key%range;
    }

    /** value will always be non-negative. */
    public void put(T key, T value) {

        int hasekey = _hase(key);
        buckets.get(hasekey).save(key,value);
        keys.add(key);
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(T key) {
        int hasekey = _hase(key);

        return buckets.get(hasekey).get(key);
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(T key) {
        int hashkey = _hase(key);
        buckets.get(hashkey).remove(key);
        if(keys.contains(key)) {
            keys.remove(key);
        }
    }
    //包含键
    public boolean containsKey(T key){
        int hashkey = _hase(key);
        return buckets.get(hashkey).get(key)==-1 ? false : true;
    }
    //查找键集
    public Set keySet(){

       return keys;
    }

}
